import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.concurrent.ConcurrentHashMap;

class StreamRank {
    List<Integer> list;
    public StreamRank() {
        list=new ArrayList<>();
    }

    public void track(int x) {
        int index=getRankOfNumber(x);
        list.add(index,x);
    }

    public int getRankOfNumber(int x) {
        int size=list.size();
        if(size==0){
            return 0;
        }
        int left=0;
        int right=size-1;
        while (left<=right){
            int mid=(left+right)/2;
            if(list.get(mid)<=x){
                left=mid+1;
            }else if(list.get(mid)>x){
                right=mid-1;
            }
        }
        return left;
    }
}












public class project {
    public int minSwaps(String s) {
        int left=0;
        int right=0;
        int ret=0;
        for(char ch:s.toCharArray()){
            if(ch=='['){
                left++;
            }else{
                right++;
            }
            if(right>left){
                ret++;
                left++;
                right--;
            }
        }
        return ret;
    }
















    public int minimumSwap(String s1, String s2) {
        if(s1.length()!=s2.length()){
            return -1;
        }
        int len=s1.length();
        int x=0;
        int y=0;
        for(int i=0;i<len;i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                if(s1.charAt(i)=='x'){
                    x++;
                }else{
                    y++;
                }
            }
        }
        if((x+y)%2!=0){
            return -1;
        }
        int ans=0;
        ans+=x/2;
        ans+=y/2;
        if(x%2!=0){
            ans+=2;
        }
        return ans;
    }





















    public int shipWithinDays(int[] weights, int days) {
        int max=0;
        int sum=0;
        for(int weight:weights){
            max=Math.max(max,weight);
            sum+=weight;
        }
        int left=max;
        int right=sum;
        while (left<right){
            int mid=(left+right)/2;
            if(judge(weights,mid,days)){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        return left;
    }
    public boolean judge(int[] weights,int mid,int days){
        int count=1;
        int len=weights.length;
        for(int i=1,sum=weights[0];i<len;sum=0,count++){
            while (i<len&&sum+weights[i]<=mid){
                sum+=weights[i];
                i++;
            }
        }
        return count-1<=days;
    }



















    public String[] findRestaurant(String[] list1, String[] list2) {
        int len=list1.length+ list2.length;
        List<Integer> list=new ArrayList<>();
        for(int i=0;i< list1.length;i++){
            for(int j=0;j< list2.length;j++){
                if(list1[i].equals(list2[j])){
                    if(len==i+j){
                        list.add(i);
                    }else if(len>=i+j){
                        list.clear();
                        list.add(i);
                    }
                    len=Math.min(len,i+j);
                }
            }
        }
        String[] ret=new String[list.size()];
        for(int i=0;i<list.size();i++){
            ret[i]=list1[list.get(i)];
        }
        return ret;
    }
}
